package com.bestcem.xm.common.core.sql;

import com.bestcem.xm.common.core.constant.Constants;
import lombok.ToString;
import org.springframework.util.CollectionUtils;

import java.util.*;
import java.util.stream.Collectors;

@ToString
public class GraphSorter<V> {
    private Set<V> vertexes;
    private Map<V, Set<V>> fromToEdges;
    private Map<V, Set<V>> toFromEdges;

    public GraphSorter() {
        this.vertexes = new LinkedHashSet<>();
        this.fromToEdges = new LinkedHashMap<>();
        this.toFromEdges = new LinkedHashMap<>();
    }

    public Set<V> getVertexes() {
        return this.vertexes;
    }

    public Map<V, Set<V>> getEdges() {
        return this.fromToEdges;
    }

    /**
     * 新增顶点
     *
     * @param vertex 顶点
     */
    public void addVertex(final V vertex) {
        if (vertex == null) {
            throw new IllegalArgumentException("arg vertex is null");
        }
        this.vertexes.add(vertex);
    }

    /**
     * 新增边
     *
     * @param from
     * @param to
     */
    public void addEdge(V from, V to) {
        if (from == null) {
            throw new IllegalArgumentException("arg from is null");
        }
        if (to == null) {
            throw new IllegalArgumentException("arg to is null");
        }

        Set<V> toVertexes = this.fromToEdges.get(from);
        if (toVertexes == null) {
            toVertexes = new LinkedHashSet<>();
        }
        toVertexes.add(to);
        this.fromToEdges.put(from, toVertexes);

        Set<V> fromVertexes = this.toFromEdges.get(to);
        if (fromVertexes == null) {
            fromVertexes = new LinkedHashSet<>();
        }
        fromVertexes.add(from);
        this.toFromEdges.put(to, fromVertexes);
    }

    public void removeFromEdge(V vertex) {
        if (vertex == null) {
            throw new IllegalArgumentException("arg vertex is null");
        }

        Set<V> toVertexes = this.fromToEdges.remove(vertex);
        if (CollectionUtils.isEmpty(toVertexes)) {
            return;
        }

        for (V toVertex : toVertexes) {
            Set<V> fromVertexes = this.toFromEdges.get(toVertex);
            if (!CollectionUtils.isEmpty(fromVertexes)) {
                fromVertexes.remove(vertex);
                this.toFromEdges.put(toVertex, fromVertexes);
            }
        }
    }

    /**
     * 拓补排序
     *
     * @return
     */
    public GraphSortResult<V> sort() {
        List<V> sortedVertexes = new LinkedList<>();

        int round = 0;
        List<V> zeroInDegreeVertexes;
        do {
            zeroInDegreeVertexes = this.vertexes.stream().filter(Objects::nonNull)
                    .filter(vertex -> {
                        Set<V> fromVertexes = this.toFromEdges.get(vertex);
                        return CollectionUtils.isEmpty(fromVertexes);
                    })
                    .collect(Collectors.toList());

            if (!CollectionUtils.isEmpty(zeroInDegreeVertexes)) {
                for (V zeroInDegreeVertex : zeroInDegreeVertexes) {
                    this.vertexes.remove(zeroInDegreeVertex);
                    this.removeFromEdge(zeroInDegreeVertex);
                }
                round ++;
                sortedVertexes.addAll(zeroInDegreeVertexes);
            }
        } while (!zeroInDegreeVertexes.isEmpty());

        GraphSortResult<V> result = new GraphSortResult<>();
        result.setRound(round);
        result.setSortedVertexes(sortedVertexes);
        result.setCircleVertexes(this.vertexes);
        result.setCircleEdges(this.fromToEdges);
        return result;
    }

    public List<V> getLongestPath(V root) {
        Map<V, V> nextMap = new HashMap<>();
        Map<V, Integer> distanceMap = new HashMap<>(this.vertexes.size());
        this.getLongestPath(root, distanceMap, nextMap, new LinkedList<>());

        V vertex = root;
        List<V> vertexes = new LinkedList<>();
        do {
            vertexes.add(vertex);
        } while ((vertex = nextMap.remove(vertex)) != null);
        return vertexes;
    }

    private int getLongestPath(V root, Map<V, Integer> distanceMap, Map<V, V> nextMap, List<V> visitingVertexes) {
        if (root == null) {
            throw new IllegalArgumentException("arg root is null");
        }

        int distance = distanceMap.getOrDefault(root, Constants.ZERO);
        if (distance > 0) {
            return distance;
        }

        Set<V> toVertexes = this.fromToEdges.get(root);
        if (CollectionUtils.isEmpty(toVertexes)) {
            return distance;
        }

        if (visitingVertexes.contains(root)) {
            return distance;
        }
        visitingVertexes.add(root);

        for (V toVertex : toVertexes) {
            int tmp = this.getLongestPath(toVertex, distanceMap, nextMap, visitingVertexes) + 1;
            visitingVertexes.remove(toVertex);
            if (distance < tmp) {
                distance = tmp;
                distanceMap.put(root, distance);
                nextMap.put(root, toVertex);
            }
        }

        return distance;
    }
}
